Liste e nodi

Il sistema operativo mantiene durante il suo periodo di attività un elevato
numero di liste di dati di vario tipo: schermi, finestre, blocchi memoria,
task, interrupt ecc. Dato che tutte queste liste hanno un numero di elementi
variabile, vengono realizzate mediante strutture linkate; ciò significa che
oltre ai dati di un elemento della lista viene inserito un indirizzo che
costituisce il puntatore al prossimo elemento in modo da costituire una
catena. Exec provvede fornendo un implementazione standard per tutte le
liste che gestisce, mettendo a disposizione quindi le routine per ricerca,
inserimento e altre che non gravano così sul programmatore; la struttura
linkata realizzata con exec viene denominata coda (in inglese queue)
bidirezionale, cioè ogni elemento oltre ad avere il puntatore all'elemento
successivo ha anche il puntatore a quello precedente; in più vi sono due
elementi particolari, Head node e Tail node che puntano rispettivamente al
primo e all'ultimo elemento della lista e necessitano per iniziare una
qualsiasi procedura di ricerca. In termini pratici tutto ciò viene tradotto
tramite una struttura:

struct Node
{
  struct Node *ln_Succ;
  struct
  Node *ln_Prec;
  UBYTE ln_Type;
  BYTE ln_Pri;
  char *ln_Name;
};

Come vedete la struttura Node non solo è costituita dai puntatori al
nodo successivo e precedente ma anche da altri dati: 'ln_Type' indica il
tipo del nodo ed assume diverse definizioni a seconda dell'ambiente in cui
viene utilizzato che specificheremo volta per volta; 'ln_Pri' indica la
priorità dell'elemento (nella lista di task indica chi ha la precedenza
sugli altri) e per questo molte volte influisce sull'ordinamento della
lista (vale a dire viene prima l'elemento con priorità più alta) di solito
'ln_Pri' assume 0; 'ln_Name' è il puntatore ad una stringa che identifica
univocamente l'elemento e può essere utilizzato per la ricerca; questi tre
elementi sono opzionali e vedremo volta per volta quando vengono
utilizzati. Questa struttura deve essere definita all'inizio dell'elemento
dati della lista; ad esempio:

struct Persona
{
  struct Node LinkNode;
  char *Nome;
  char *Cognome;
  int anni;
  char *codicefis;
};

E' possibile comunque utilizzare una struttura "minima" e cioè senza
ln_Type, ln_Pri, ln_Name nella quale non fossero necessarie, denominata
MinNode:

struct MinNode
{
  struct MinNode *min_Succ;
  struct MinNode *min_Pred;
};

Occorre mantenere anche le informazioni riguardanti l'indirizzo del nodo
di testa e di quello di coda, per cui si utilizzerà la struttura List:

struct List
{
  struct Node *lh_Head;
  struct Node *lh_Tail;
  struct Node *lh_TailPred;
  UBYTE lh_Type;
  UBYTE lh_Pad;
};

lh_Type è un codice numerico che indica il tipo di lista (o meglio qual è
il contenuto di codesta); lh_Pad non contiene alcun informazione e serve
solamente ad assicurare l'allineamento a word di dati eventualmente presenti
dopo; i primi tre valori sono puntatori a nodi e rappresentano la testa e la
coda della lista; tale modo di conservare i puntatori non è quello
convenzionale in quanto normalmente, si considerano i puntatori agli
elementi di testa e di coda e si devono gestire una serie di casi
particolari (inserimento in testa, inserimento in una lista vuota ecc.)
implementando così una serie di verifiche di sicurezza; in questa struttura
invece sono direttamente presenti gli elementi di testa e di coda da
considerare "immaginari" perché non contengono alcun dato; in termini
pratici lh_Head ed lh_Tail rappresentano rispettivamente il puntatore
all'elemento successivo e all'elemento precedente di questo nodo di testa
immaginario, ed il primo è il puntatore al primo nodo effettivo della
struttura dati, ed il secondo vale 0; mentre lh_Tail e lh_TailPred
costituiscono il successivo e il precedente del nodo di coda immaginario e
valgono 0 per il primo e l'indirizzo dell'ultimo nodo effettivo per il
secondo (lh_Tail è condiviso perché vale sempre 0); capite che facendo così
si eliminano tutti i casi particolari e con essi le verifiche necessarie per
implementarli; infatti in caso di lista vuota esistono comunque due elementi
(la testa e la coda immaginari), per cui l'inserimento in una lista vuota è
uguale all'inserimento normale, oppure l'inserimento di un nodo in testa
alla lista equivale realmente ad un inserimento qualunque, poiché il nodo di
testa della lista si trova sempre dopo quello immaginario è quindi non è
realmente in testa anche se al programmatore sembra che sia così.
Dopo questa spiegazione da cane che si morde la coda, per inizializzare una
lista e gestirla vi sono comunque delle funzioni di exec apposite e che
quindi non richiedono nessuna operazione aggiuntiva da parte del
programmatore.

struct MinList
{
  struct MinNode *mlh_Head;
  struct MinNode *mlh_Tail;
  struct MinNode *mlh_TailPred;
};

questa struttura viene utilizzata nella stessa maniera di List salvo che per
questa non vanno specificate le informazioni aggiuntive. Osserviamo ora le
funzioni messe a disposizione da Exec per la gestione delle liste:

NewList(Lista);

dove Lista è il puntatore ad una struttura List; NewList effettua
l'inizializzazione della lista vuota ed imposta correttamente i valori di
Lista.

AddHead(Lista,Nodo);
AddTail(Lista,Nodo);
Enqueue(Lista,Nodo);

dove Lista è sempre il puntatore ad una struttura List (se è appena creata
occorre inizializzarla con NewList) e Nodo è il puntatore alla struttura
Node da inserire nella lista; AddHead serve per inserire il nodo in testa
alla lista, AddTail per inserirlo in fondo ed Enqueue per inserire il nodo
in modo da mantenere la lista ordinata per priorità (ln_Pri); tenete
presente che Enqueue deve operare su una lista già ordinata (vale a dire
ogni elemento della lista deve essere stato inserito con questa funzione,
oppure facendo attenzione che la posizione a seconda della priorità sia
giusta); con Enqueue, il nodo verrà inserito dopo l'ultimo elemento con
priorità maggiore o uguale a quella sua ed inoltre, il primo elemento della
lista (quello di testa) ha priorità maggiore (quindi ordinamento numerico
decrescente); questa funzione non può essere utilizzata ovviamente con liste
minime.

Insert(Lista,Nodo,NodoPrec);

dove Lista e Nodo hanno lo stesso significato di prima e NodoPrec è il
puntatore ad un nodo della lista "Lista"; Insert inserirà il nodo "Nodo"
nella lista "Lista" nella posizione immediatamente successiva a NodoPrec.

Remove(Nodo);
Nodo = (struct Node *)RemHead(Lista);
Nodo = (struct Node *)RemTail(Lista);

Remove rimuoverà il nodo "Nodo" dalla lista in cui è presente; quì non
occorre specificare nessuna lista giacché in Nodo stesso sono presente tutte
le informazioni per la sua eliminazione (puntatore al nodo precedente ad a
quello successivo); RemHead e RemTail rimuovono rispettivamente il nodo di
testa e quello di coda e ne ritornano l'indirizzo in caso serva (per la sua
deallocazione o per altri usi).

Nodo = (struct Node *)FindName(Lista,nome);

dove nome è il puntatore ad una stringa; FindName ricercherà il nodo con
nome (ln_Name) "nome" nella lista "Lista" e se lo troverà ritornerà il suo
indirizzo altrimenti ritornerà NULL; questa funzione non può essere
utilizzata con le liste minime.